#include <stdio.h>
#include "algo_quickSort.h"

#define numElement 10
#define swap(type, i, j) {type t = i; i = j; j = t;}

// an auxilarary function for partitioning an array
// perform in-place partition
int partition(int a[], int startIndex, int endIndex, int partitionIndex) {
	// swap the elements at partitionIndex and endIndex
	swap(int, a[endIndex], a[partitionIndex]);
	// rearranging the array in place
	int pivot = a[endIndex];
	partitionIndex = startIndex;
	for (int i = startIndex; i < endIndex; i++) {
		// move the elements smaller than the pivot to the left
		if (a[i] <= pivot) {
			swap(int, a[i], a[partitionIndex]);
			partitionIndex++;
		}
	}
	// move the pivot to proper position
	swap(int, a[endIndex], a[partitionIndex]);
	// return a new partitionIndex
	return partitionIndex;
}

void quickSort(int a[], int startIndex, int endIndex) {
	if (startIndex >= endIndex)
		return;
	int partitionIndex = (startIndex + endIndex)/2;
	// partition the array and find a new position of partitionIndex
	partitionIndex = partition(a, startIndex, endIndex, partitionIndex);
	// perform quick sort the part of the array before partitionIndex
	quickSort(a, startIndex, partitionIndex-1);
	// perform quick sort the part of the array after partitionIndex
	quickSort(a, partitionIndex+1, endIndex);
}

void test_algo_quickSort() {
	int data[numElement] = { 12, 1, 3, 9, 9, 8, 2, 7, 10, 15 };

	printf("Before sorting.\n");
	for (int i = 0; i < numElement; i++) {
		printf("%d", data[i]);
		if ( i < numElement - 1 )
			printf(", ");
		else
			printf("\n");
	}
	printf("\n");
	quickSort(data, 0, numElement-1);
	printf("After quick sorting.\n");
	for (int i = 0; i < numElement; i++) {
		printf("%d", data[i]);
		if ( i < numElement - 1 )
			printf(", ");
		else
			printf("\n");
	}
}
